/**
 * Created by L.jp
 * Description:一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * User: 86189
 * Date: 2022-01-15
 * Time: 10:29
 */
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
    //如果要求只出现一次的数字的一个数字，那么只需要让数组每一个元素异或，最终的结果就是只出现一次的数字
    //对于这个题目求只出现一次的两个数字原理也是一样的
    //1、首先进行整体的异或，发现最终得到的这个数二进制位上是有多个1的，说明最终两个不同的数在不同的比特位上是不同的
    //2.比特位要么是0要么是1，我们可以利用flag=1的依次左移跟刚刚最终得到的结果按位与来找到第一个1出现的位置，找到后就退出左移的循环
    //3.用此时1出现位置的flag去跟数组的每一个数按位与，如果等于0说明这个数当前位置没有1，这样就可以把这些数分为两组，一个是当前位置是1，一个是当前位置不是1
    //4。在这两种情况下，然后再让给定的参数分别与数组每一个数异或，最终的结果就分别是不同的两个数。
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || num1 ==null || num2 == null){
            return;
        }
        //给定一个变量用于异或整体
        int ret=array[0];
         num1[0]=0;
         num2[0]=0;
        for(int i=1;i<array.length; i++){
            ret^=array[i];
        }
        //这个结果一定不为0，找到这个数的二进制位为1的位置，按照从高位到低位的顺序查找
        int size=Integer.SIZE;//32个比特位
        int flag=1;
        while(size>0){
            size-=1;//左移
            //如果flag左移后跟ret按位与的结果不为0，说明当前二进制位是1
            if(((flag<<size) & ret)!=0){
                flag<<=size;
                break;//找到了这个位置，退出
            }
        }
        //然后根据当前位是0还是1的情况分组
        for(int i=0;i<array.length; i++){
            //array中肯定有一一些数是当前二进制位不是1的，那么他们与flag当前位的1按位与就是0了，即使有多个数，但是相同的数只要异或就是0
            if((flag&array[i])==0){
                //可以用参数传回结果
                num1[0]^=array[i];//只剩下最后一个当前二进制位是0，但是是出现一次的数字
            }else{
                //当前二进制位是1，那么按位与的结果就不是0，那么最后异或的结果就是另一个出现一次的数字
                num2[0]^=array[i];
            }
        }
    }
}
